package com.ljy.my_study.leetcode.k个一组翻转链表;

/**
 * @author James
 * @date 2018年9月16日
 */
public class TestMain {

	// 给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
	//
	// k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
	//
	// 示例 :
	//
	// 给定这个链表：1->2->3->4->5
	//
	// 当 k = 2 时，应当返回: 2->1->4->3->5
	//
	// 当 k = 3 时，应当返回: 3->2->1->4->5
	//
	// 说明 :
	//
	// 你的算法只能使用常数的额外空间。
	// 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		int[] arr= {5,4,2,7,12,3,68,12,21,87,9,19};
		int[] arr1= {1,2};
		int[] arr2= {1,2,3,4,5};
		int[] arr3= {1,2};
		
		ListNode head=testMain.createListNodeKGroup(arr2);
		testMain.printKGroup(head);
		head=testMain.reverseKGroup(head, 5);
		testMain.printKGroup(head);
	}
	
	public ListNode createListNodeKGroup(int[] arr) {
		if(arr.length==0) {
			return null;
		}
		ListNode head=new ListNode(arr[0]);
		if(arr.length==1) {
			return head;
		}
		ListNode thisNode=head;
		for(int i=1;i<arr.length;i++) {
			thisNode.next=new ListNode(arr[i]);
			thisNode=thisNode.next;
		}
		return head;
	}
	
	public void printKGroup(ListNode head) {
		if(head==null) {
			System.out.println("");
			return;
		}
		StringBuilder sb=new StringBuilder(head.val+",");
		ListNode thisNode=head.next;
		while(thisNode!=null) {
			sb.append(thisNode.val+",");
			thisNode=thisNode.next;
		}
		System.out.println(sb.subSequence(0, sb.length()-1));
	}

	public ListNode reverseKGroup(ListNode head, int k) {
		if(head==null||k==0) {
			return head;
		}
		
		ListNode newHead=head;
		boolean isFirst=true;
		int num=0;
		ListNode[] nodeArr=new ListNode[k];
		ListNode thisNode=head;
		ListNode lastArrNode=null;
		while(thisNode!=null&&thisNode.next!=null
				||(thisNode!=null&&thisNode.next==null&&num<=k)
				||(thisNode==null&&num==k)) {
			if(num<k) {
				nodeArr[num]=thisNode;
				thisNode=thisNode.next;
				num++;
			}else {
				ListNode reverseNode=reverse(nodeArr);
				if(isFirst) {
					newHead=nodeArr[k-1];
					lastArrNode=nodeArr[0];
					isFirst=false;
				}else {
					lastArrNode.next=nodeArr[k-1];
					lastArrNode=reverseNode;
				}
				reverseNode.next=thisNode;
				num=0;
				nodeArr=new ListNode[k];
			}
		}
		
		if(isFirst) {
//			if(nodeArr.length<=num-1||num-1<0) {
//				return head;
//			}
//			if(num<k) {
//				
//			}
//			newHead=nodeArr[num-1];
			return head;
		}
		
        return newHead;
    }

	public ListNode reverse(ListNode[] nodeArr) {
		StringBuilder sb=new StringBuilder();
		for(int i=nodeArr.length-1;i>0;i--) {
			nodeArr[i].next=nodeArr[i-1];
			sb.append(nodeArr[i].val+",");
		}
//		System.out.println(sb.append(nodeArr[0].val).toString());
		nodeArr[0].next=null;
		return nodeArr[0];
	}
	
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\"} ";
		}
	}

}
